This invention relates to a detection system for determining information concerning the location of objects, and which can be extended go determine movement and orientation and even physical parameters such as shape of objects in a specified environment. The invention can be applied to people and animals as well as inanimate objects such as furniture, machines, vehicles, equipment and the like, and in this connection object is intended to include any movable entity.
Location systems are known which allow the presence or absence of an object in a specified environment (such as a room) to be confirmed or denied, and relative to one or more reference points to identify where in the environment the object is located.
EP 0485879 describes a system for locating vehicles in automatic guidance transport systems. Ultrasound is employed as a distance measuring medium whilst an infra-red link allows communication between vehicles.
WO95/14241 describes a tracking system which enables a spotlight to follow a person on a stage carrying a transponder. Again infra-red signals are used to instigate ultrasonic transmissions to determine the position of the transponder and therefore the person. The spotlight is moved accordingly.
EP 0591899 describes another spotlight controlling system for tracking a moving target (actor on a stage) carrying a transponder. Here radio transmissions establish the communication link and ultrasound transmissions are employed to determine distance and position.
These systems do not measure characteristics other than position and are limited with regard to the number of objects which can be tracked due to the length of time needed for each ultrasound transmission to die away, which is inherent in any such system, and it is an object of the present invention to provide a detection system capable of track-in more objects, which can be modified to allow orientation, rotational movement and linear movement to be determined and tracked and will further allow for control of operable devices on or associated with the object.
A system embodying the invention enables the position of each of a plurality of labelled objects in a specified environment to be determined by determining the transit time of slowly propagating energy transmitted from a transmitter on each labelled object, to a plurality of receivers positioned at fixed points in or around the specified environment, and computing therefrom the actual distance of the transmitter from the receivers, wherein the transmission of the slowly propagating energy is initiated by a burst of high speed propagating energy from a master transmitter located so as to cause transmitted bursts of such high speed energy to enter the said environment, and the transmitter is associated with a receiver adapted to respond to an appropriately encoded burst of such high speed energy, to thereby initiate a burst of slowly propagating energy therefrom, (each said transmitter/receiver combination being referred to as a transponder) and in order to allow the system to adapt to different numbers of transponders and differing demands for service (eg frequency of position determination per transponder or object), a coordinating control system is provided for determining the order in which the object mounted transmitter/receiver combinations are to be addressed and triggered by the transmissions from the master transmitter, in response to updatable information relating to the objects and related service demands.
Preferably each of the said plurality of receivers is adapted also to be responsive to said burst of high speed energy, so as to identify the beginning of a window of time within which a slow speed energy burst may arise and be received thereby. The burst may be the same burst as is sent to trigger one of the transmitter/receiver units transponders to transmit a slowly propagating wave, for time measurement.
Alternatively the said plurality of receivers may be connected by a network of cables and the reset signals and the polling of the time values may be achieved via the network.
Preferably the receivers include a latch to retain information about the time at which the beginning of a burst of slow speed energy is received after the beginning of each said time window.
Preferably the receivers are scanned (ie polled) so as to recover the time information and reset the latches.
Preferably computing means is provided to associate the time information with the receiver from which the times have been obtained, and generate a transmit time for each receiver.
Preferably the computing means is programmed to convert the transit time into distance values and using position data relating to the receivers stored in a memory, to compute therefrom the position of the object mounted transponder from each of the receivers, and therefore, by geometry its position relative to one or more fixed points defining the specified environment.
By encoding the high speed energy transmission, so a plurality of different slow speed signal transmitters all located in the same specified environment, can be triggered in turn, so that during a sequence of time windows, position data relating to each of the slow speed signal transmitters in the environment can be obtained, the data in each window relating specifically to one only of the object mounted transponders.
Typically the slow speed signals are acoustic or ultrasonic signals and the high speed signals are electric currents or voltage or visible or invisible electromagnetic radiation such as IR, UV or radio signals.
Encoding of the high speed signals may be by way of frequency or amplitude or phase modulation or pulse coding or any combination thereof.
Preferably digital encoding techniques are employed, if only to ensure adequate signal to noise ratios can be achieved.
Background Theory to Position Determining Systems
Such systems are based on the principle or location by multilateration. For each object that is to be located, the straight-line distances are measured from a point on that object to a number of other points in the environment whose positions (in some frame of reference) are already known. Given enough distances, and a suitable geometry of the endpoints between which they are measured, it is possible to derive a position for the object.
To determine the distances between objects and points in the environment, transmitters and receivers are placed on them and measurements are made of the times of signal pulses being generated and received. The system can be used to measure round trip delays, or alternatively can give the difference in the one-way delays for signal pulses sent simultaneously (or with known time offsets). If the one-way delay in two media are dt1 and dt2, then
D=dt1xe2x88x92dt2,
and
if the (predictable) velocities of propagation in the two media are v1 and v2, and the distance between transmitter and receiver is R, then
R=D/(1/v1xe2x88x921/v2).
It may be seen that if v2 is much greater than v1, then the range calculation can be approximated by
R=Dv1.
Thus, if, for example, radio and ultrasonic signals are transmitted simultaneously through space then the equation R=Dv1 will give sufficiently accurate results for the limited range of distance likely to occur in an indoor environment, such as a typical house, room, office or even small factory unit or warehouse.
It is not necessary to transmit both fast and slow speed signals simultaneously. A radio pulse for example, can be treated as if its travel time is zero (i.e. independent of range), and it can thus simply be used as a trigger signal. However the flight times of the slow signal pulses (e.g. ultrasonic pulses) can be accurately measured by synchronising the transmitter and receiver units, as by a timing pulse generated by a suitable controller.
Reflections from other objects in the transmitter""s environment may cause multiple signals to arrive at a receiver. Any direct-path signal from the transmitter to the receiver should arrive before these reflections, so that in general all pulses arriving at a receiver after the first one should be ignored. For this reason, it is important that the width of the pulse sent by the transmitter is as short as possible, so that the direct-path and reflected signals may be identified optimally.
Problems in Such Systems
It should be noted that diffraction of the pulse signal may also occur, and this will produce similar effects to the unwanted reflections.
Once a set of distances from the transponder transmitter to the receivers has been found, the system is programmed to attempt to derive a position of the transponder.
It is possible that some receivers will have detected no signal from the transponder transmitter, due to obstructions, directionality of the transmitting element, etc. These receivers must be excluded from further consideration.
It is also possible that the first pulse detected by a receiver is a reflected or diffracted signal. (This may occur, for example, if the direct signal path is obstructed). In this case, the computed distance will be greater than the true distance, and errors would be introduced into the position for the transmitter that is reported by the system if that incorrect distance is used in the position calculation. In general the computed distances would not identify a unique point (or more generally small volume). If this occurs the erroneous computed value has to be identified and eliminated.
Reflected and diffracted signals that arrive at receivers can sometimes be distinguished from direct path signals by inspection of the received pulse shape, and thereby inaccurate measurement eliminated.
If this is not possible, other ways must be found of comparing the distances measured by receivers for example by comparing measurements made by pairs of receivers in order to identify and eliminate erroneous signals.
One way of doing this is to compare the distances reported by all pairs of receivers that have detected a slow speed signal. It can be shown geometrically that the difference of the measured distances from two receivers to a transponder transmitter cannot be greater than the straight-line distance between the two receivers, if the measured distances are accurate. Thus, if a pair of receivers is found for which the measured distances to the transponder transmitter do not satisfy this criterion, the receiver that has reported the longer distance can be excluded from further consideration, since reflections and refractions in general will tend to produce longer distance values than the true straight-line distance.
Distance Computation and Position Fixing
Having performed this algorithm, the system may be adapted to attempt to fit a non-linear regression model to the remaining distances, by performing an iterative regression computation on the data.
If this fails to converge, the system may be programmed to report that it is unable to calculate the position of the transmitter using the available data.
If the iteration converges, however, studentised residuals are preferably calculated for the distances, and the system preferably determines the variance of the distance data.
Reflected signals will tend to produce large value, so that if the variance is below a predefined, acceptable level, the system can be programmed to conclude that all erroneous signals have been identified and eliminated.
If the variance is greater than an acceptable level, signals derived from the receiver associated with the distance that has the largest positive studentised residual is assumed to have resulted from at least one reflection and these signals are first excluded from consideration. The system is programmed to attempt to fit the model again.
This procedure involving the deletion of receivers and signals from consideration is repeated as necessary, until the variance of distance data from the remaining detectors is sufficiently small.
This process is of course only valid if a large enough number of signals/receivers still remain when the small variance is noted.
At any stage in this process, it may be found that the geometry or number, or both of the remaining receivers under consideration is insufficient for a three-dimensional position for the transponder transmitter to be calculated. For example, all the remaining receivers may be in line.
If this occurs, the system is adapted to abort the computation and report that insufficient information has been gathered to fix the position of the transmitter at that time.
In an application of this procedure, when the system criteria indicate that all receivers that may have detected an erroneous signal have been eliminated from consideration, a non-linear regression model has been fitted to the distances calculated from the pulse times determined by the remaining receivers, and a transponder transmitter position has been found, the system may use this information for various purposes, or it may transmit the information to other interested parties.
Before transmitting a second slow speed signal the system preferably waits for reverberations of the previous distance-measuring pulse to die out before attempting to repeat the above procedures to get another fix for the transponder transmitter position. Obviously, the time the system must wait for this to happen will depend on the characteristics of the transmission medium and the transmitter""s environment. This may be determined empirically, or by adaptation such as by self-learning.
In one embodiment of the present invention, there is provided a detection system for determining information concerning at least the position of an object, using signal pulses respectively of high and slow propagation speeds, comprising at least three fixed, non-collinearly distributed slow speed signal responsive receivers, at least one transponder transmitter unit for transmitting slow speed signal pulses, mounted on the object, means for generating and transmitting high speed signal pulses to synchronise signal pulse transmission from the transponder with the commencement of a reception-sensitive period at a receiver and means for computing signal pulse reception times and correlating differences therein to determine the required information about the position of the object.
In another embodiment, a separate transmitter is located on each of two or more objets in the specified environment and each transmitter includes a high speed signal responsive receiver adapted to respond to only one of a plurality of high speed signals, and the separate transmitters are triggered in sequence by a transmitter of high speed signals which is adapted to transmit uniquely one of the plurality of possible high speed signal at the beginning of each timeframe.
The invention can be adapted to identify and log movements of two or more objects in the same area/space, by mounting a transponder transmitter on each object and providing each transponder with a unique address, so that each transmitter can be triggered in turn and the position of the relevant object determined in a sequence.
It is not only necessary to trigger transponder transmitters uniquely, but also necessary to restrict transmissions from multiple objects so that they do not interfere with each other, by making sure that the transmissions do not overlap in time in the same space.
In accordance with the invention, this is arranged by a coordination device which addresses the transmitters, and sends address information to them as part of a regular timing synchronisation signal. For example, the slow speed signal transmitters, each with their own high speed signal receiver and unique address, could be placed on the objects to be located, and access to th space in which the distance-measuring pulses are transmitted is divided into discrete timeslots, the duration of each timeslot being the time needed for reverberations of pulses to die down. At the start of each timeslot, the coordinating device is adapted to send out a high speed timing-synchronisation signal (typically a radio signal) which consists of an address and a timing pulse. All the transponders on the objects will receive this signal, and each compares the received address with its own. If the addresses are the same, that transponder one transmits a slow-transmission-speed distance measuring pulse, when the timing pulse is received.
The frequency at which addresses are transmitted by the coordinating device may be varied, either during set-up, or based on information obtained from previous addressings.
Thus during set-up an object which will normally be static and remain for long periods of time in one place, can be identified as such, and its address only transmitted infrequentlyxe2x80x94say once every 5 minutes or once every hour. However objects which it is known in advance are likely to move (or be moved) within the space, can be identified as mobile, and their transponder addresses transmitted more frequentlyxe2x80x94eg once every minute, or every few seconds, or even more often if the system capabilities permit.
In a more sophisticated arrangement, a memory in the coordinating device may be used to store against each address, an item of information which indicates the frequency of position changes, for that address, detected by the system during some predetermined period of time (which might be minutes, hours or days depending on the environment and the nature of the objects carrying the transmitters). The stored item of information is employed to determine how often each address is broadcast. If the item of information changes in value, indicating an increased or decreased frequency of movements of the address within the space, the coordinating device can respond appropriately and increase or decrease the frequency of transmissions of the address received.
The system can also be used to determine the true orientation of an object, by comparing the position of two or more transponder transmitters mounted on the object.
If an object is rigid and stationary (or moving slowly or predictably enough) and a number of transmitting elements are placed at known points on the object, the positions of all the transmitters can be found in three dimensions. Since the fixed spatial relationship between the transmitters on the object is known, as well as their measured positions in three dimensions, it is also possible to determine the orientation of the object.
Depending on the knowledge of the capability of movement of an object, one or more transponder transmitters located thereon will enable the position and orientation of the object to be determined. Thus an object mounted for rotation about a fixed axis and only capable of that movement will generally only need one offxe2x80x94axes transmitter to be mounted thereon to allow its rotational position to be computed.
If two spaced apart transmitters are mounted on an object, more information about rotation and position can be determined to advantage.
If orientation is to be determined efficiently and quickly, it is preferable to cause the two or more transmitters on the object to transmit in succession.
If the object is moving, then the same pattern of addressing is preferably maintained so that changes (caused by movement) in the actual and/or relative positions of the transmitters will be as small as possible, and the most accurate description of each orientation as well as the movement of the object will be obtained.
A preferred embodiment of the invention comprises a system for determining the position of an object in a specified environment in which the transit time is determined of slowly propagating measurement energy transmitted from a transmitter on the object to a plurality of receivers positioned at fixed points in or around the specified environment, and in which the distance of the transmitter from each receiver is computed from the times taken for the measurement energy to propagate from the object to some of the receivers, and wherein the slowly propagating measurement energy is initiated by a trigger burst of energy having a higher speed of propagation from a master transmitter which is located so as to transmit trigger bursts into the environment to initiate the measurement energy transmitter on the object of interest, and wherein a plurality of such transmitters are located on different objects and/or points of the same object within the environment, and each transmitter of measurement energy is associated with and controlled by signals from a receiver responsive to trigger burst transmissions, and the latter are encoded and/or transmitted at different frequencies so that the receivers located throughout the environment can be individually addressed from the master transmitter,
characterised in that
a coordinating control system is provided for determining the order in which the object mounted transmitter/receiver combinations are to be addressed and triggered by the transmissions from the master transmitter, together with memory means for storing relevant information about the different combinations with reference to their addresses, by which the order can be determined.
The coordinating control system memory means typically stores a unique address for each of the receiver/transmitter combinations, and the control system is programmed to encode the transmissions using the address information so as only to address the transmitters individually.
Preferably in addition to the unique address for each receiver/transmitter combination, at least one additional item of information (a weighted hierarchy indication for schedule positioning, or xe2x80x9cWHISPxe2x80x9d) is stored in a manner which can be associated with each unique address, and the control system is programmed to select from the addresses that of the receiver/transmitter combination next to be polled, using the WHISP values to determine the order of addressing.
The coordinating control system may be separate from or form an integral part of the master transmitter.
WHISP Options
A WHISP may be stored for each unique address, and it is the WHISP which must be changed to adjust the subsequent addressing of the transponders.
Alternatively a set of standard WHISPS may be stored and an association between each unique address and one of the standard WHISPS is stored for each unique address, so that an appropriate WHISP is linked to each unique address. In that event only the associations need to be changed so as to influence the subsequent addressing or the transponders. Likewise a change to one (standard) WHISP will mean that all the associated addresses will be given a new hierarchial position.
For complete flexibility unique addresses, WHISPS, (and/or the associations between unique addresses and WHISPS) can all be changed to allow for the entry or exit of transponders into and out of the environment, and to alter the manner in which those in the environment will be addressed by the coordinating control system.
In one example the WHISP may be a simpler logic 1 or 0 to indicate whether the transponder combination is to be addressed or not.
The WHISP may comprise a priority or weighting measure to determine the order or rate at which the transponder is to be addressed.
The WHISP may comprise two items of information, firstly for example the length of time since the transponder was last addressed (which may be continually updated by clock information) and secondly for example a rate of interrogation figure to be achieved by the system for that transponder.
Assembly of Address Lists (Scheduling)
The coordinating control system may compile a list of transponders to be addressed in a sequence by interrogating all of the unique addresses and their related WHISPS and compiling the order in which they are to be interrogated using the current WHISP information.
Thus in one arrangement the coordinating control system may create a schedule of unique transponder addresses using the WHISP data, and arrange the order of the addresses in the schedule, and therefore the order in which they are to be interrogated. The schedule is then used to determine the encoding of each trigger burst from the master transmitter and the order in which the transponders are thereby interrogated.
In this arrangement, updating may be performed in two different ways. Thus in one mode, any changes which are required to be made to WHISP data may be held over pending the end of the interrogation of the current schedule of addresses, whereupon the WHISP data is updated prior to the compilation of the next schedule.
Interruptions to Scheduling
In an alternative mode, a change to a WHISP may be permitted to interrupt the running of a particular schedule if the unique address or addresses associated with that WHISP is/are still to be interrogated, but is held over to update the WHISP data before the next schedule is compiled if the particular address or addresses has/have already been interrogated in the current schedule.
In either mode, the system may include an emergency override to allow the transponder triggering in accordance with the current schedule to be terminated immediately, and for a new schedule to be immediately compiled, taking account of the WHISP change associated with, or entered with or after, the emergency override instruction.
Dynamic Scheduling
An alternative and more flexible approach to scheduling involves merely determining from all available data existing just before the next trigger transmission is due, the next transponder address which should be interrogated, using a suitable algorithm and high speed processing, and the development and implementation of one particular algorithm for performing this function is set out below.
Determination of Dynamic WHISP Scheduling
Changes to WHISP data may occur as a result of a lapse of time, the arrival o a particular time or date, or by interaction with an application running on a computer (which may be part of the position determining system, or the coordinating control system, or another computer altogether), or by, the entry of data by an operator for example to indicate that the system should cease its scheduled transponder position determining function and for example seek one particular transponder (which may for example relate to that on a particular person or object believed to be within the environment).
Additionally or instead, environment related information may be allowed to create an interruption to permit or cause WHISP data to be altered, such as an increase or decrease in temperature, light level, or sound level or like, either within the environment or within a separately monitored environment, or by transducer originating signals linked for example to the movement of an object either within the environment; within an adjoining environment; or for example by the opening of a door communicating between one environment and another.
Independent Movement Sensing
The movement of an object within the monitored environment or an adjoining environment may we detected by means of a movement sensor such as a trembler switch, associated with the object. If so a radio or hard-wired communication channel may be required between the sensor and the coordinating control system.
WHISP Data Changes
References to changes to WHISP data, include changing the WHISP data stored in a unique memory means linked to one of the unique addresses, or changing the association between a transponder address and a plurality of standard WHISPS, depending on whether a separate WHISP is stored for each address, or whether a number of standard WHISPS are stored and associations between them and the different event transmitter addresses are stored.
Operation of the Scheduler
According to another aspect of the invention, the scheduler may be adapted not only to determine the order in which the transponders are to be interrogated but also the rate of interrogation of any one transponder.
This may for example be a fixed rate associated with the particular transponder address, which rate is entered as a second item of information in each WHISP.
Alternately in another example, the second item of information may be an adjustable rate value, which can be altered in relation to variations in a parameter monitored by a transducer or sensor. The parameter may for example be temperature, light level, sound level or the like, or may be a value which can be adjusted by an operator, or in relation for example to a parameter such as the time, or the date.
According to a particularly preferred aspect of the invention the rate parameter associated with each WHISP itself may be a dynamic variable, whose instantaneous value is determined for example by whether a variation has occurred in the detected position of a transponder carried by an object.
Resource Allocation
If the object(s) are stationary, the position(s) of the transponder(s) carried by the object(s) will be substantially identical each time the system interrogates the relevant transponder(s). By comparing the last noted position(s) with the current noted position(s) and applying a tolerance band to cover minor variations introduced by the measuring process, the system can be programmed so as to reduce the frequency at which any one transponder (or group of transponders) is interrogated, down to a relatively low level, thereby reducing the traffic on the system and allowing more time to be available for more frequent interrogation of transponders positioned on objects which are moving, and whose positions therefore are likely to vary from one reading to the next.
In order to monitor a rapidly moving object interrogations spaced by less than a second may be needed in order to track its movements, and it is of great advantage to reduce the rate of consideration of transponders on other objects which are essentially static, or only moving very slowly or in a predictable pattern.
Tracking Rate Variation
According to another preferred feature of the invention, the system may be programmed to utilise a third item of data within a WHISP, and to increase the tracking, (ie frequency of interrogation) of a transponder of a first object if a second object having such a third item of information stored as part of its WHISP is perceived by he position determination of the transponder on the second object, to have moved close to the first object.
Thus for example the WHISP of a transponder address of a human being may carry such a third item of information, so that if the transponder linked to the person concerned is seen by the system to approach an object which is normally stationary and whose transponder would otherwise be interrogated perhaps only once every 5 minutes, the interrogation rate of the transponder associated with the stationary object may be increased in anticipation of the possibility that the person may suddenly move it.
Thus by allowing for the instantaneous adjustment of the next transponder address which is to be interrogated, a fully dynamic system can be created since it allows the scheduler to alter not only which transponder is to be interrogated but also the rate at which different transponders are to be addressed with complete flexibility, thereby to follow changes and developments in an environment, with little or no delay. The system can therefore be thought of as having very low hysteresis and by including pre-programmed items of information in each WHISP, which can alert the system to the likelihood of changes occurring, so sudden changes in the environment can be followed almost immediately they occur.
Basic Assumptions to Allow Algorithm Parameters to be Determined
By way of example let us consider a location system that uses a set of ultrasound receivers placed at known positions on a ceiling in a room to detect ultrasonic signals from an ultrasound transmitter attached to an object in the room. By determining the times-of-flight of those signals from the ultrasonic transmitter to the ultrasound receivers, we may calculate in the three dimensions the position of that object in the room. The a system can be extended to locate more than one ultrasonic transmitter in the room, provided each has a unique address so that they can be triggered separately, typically by serially polling the transmitters.
In order to accurately measure the signal flight-times, a central coordinating device triggers the transmitter, at the same time as a reset signal is sent to the ultrasound receivers, typically over a wired network. Synchronisation between the transmitting and receiving elements of the system is thus achieved. To ensure that only one transponder is triggered (where two or more transponders exist in the room and so as to prevent the confusion that would be caused if ultrasound receivers were to detect ultrasound signals from more than one source), each ultrasonic transmitter is controlled by a radio receiver and is triggered by the transmission of a suitable radio signal into the room. Each receiver includes a unique address. The radio signal contains one such unique address. Upon receipt of the radio signal, each radio receiver compares the transmitted address with its own, and, if the addresses match, its ultrasonic transmitter is triggered to emit a short pulse of ultrasound.
The central coordinating device has to allow for reverberations and reflections of each transmitted pulse ti die away (so that the ultrasound receivers detect ultrasound from only one source) before triggering another ultrasonic transmitter. For a typical room, the time needed to allow all such sounds to die away can be of the order of 20 ms.
It can be seen, therefore, that there is a limit on the number of ultrasonic transmitters which such a location system can trigger in any time period. The time between each radio addressing message is called a timeslot, and only one transmitter can be interrogated and triggered within each timeslot.
Efficient distribution of the timeslots between ultrasonic transmitters to be located is clearly a priority, and this distribution should take account of the different rates at which location information about particular objects is desired. For example, the system might normally monitor transponders carried by people (who move often) at least once each second, whereas it might monitor those attached desks, filing cabinets or workstations (which move infrequently) only once a minute. If, however, a monitored person walks up to a particular workstation, the system may be programmed thereafter to monitor that workstation""s position once a second at least while the person is noted as being in the vicinity, because it is then more likely to be moved.
A further constraint on the allocation of timeslots can arise when members of a group of transponders need to be interrogated in consecutive timeslots. This is advantageous when the positions or the transponders in the group are to be used to determine both the location and orientation of an object, such that any motion of the object between readings can make the derived information inaccurate.
As mentioned above, the process of timeslot distribution is called scheduling, and software, typically in the form of an algorithm for performing this function, will be called a Scheduler.
The priority level assigned to each different transponder is called its Location Quality or Service (LQoS).
The LQoS of a transponder may also be changed at any time, and subsequent timeslot allocation needs to take account of any such changes.
The Scheduler provided by the present invention is designed to accommodate LQoS changes; to have the appropriate long term behaviour; to assign timeslots to transporers based on their Location Quality of Service (LQoS); and furthermore to deal with service demands which are greater or less than the system capacity, by scaling excessive requests fairly in the former case, and padding with dummy timeslot assignments in the second. It is also capable of adjusting timeslot assignment to allow a group of transponders to be located consecutively.
Scheduler Implementation
Let us consider a system having the following parameters:
(1) The length of a timeslot is 40 ms (ie the system is capable of determining 25 positions per second)
(2) The transmitters each have a unique 16-bit address
(3) The reserved address 0 is not allocated to any transmitter.
(4) Every transponder is also a member of one transponder group, also identified with a 16-bit number (again, identifier 0 is reserved)
(5) The scheduler is a CORBA-based distributed software programme (Object Management Group, The Common Object Request Broker; Architecture and Specification. Revision 1.1, OMG Document number 91.12.1, December 1991) running on a workstation.
(6) Location Quality of Service (LQoS) is expressed as an integer representing the desired period of positioning (eg an LQoS of 25 requests one position every 25 timeslots, ie once per second).
In accordance with the invention, the Scheduler is adapted to maintain a scheduling table stored in memory. Each row of the table contains six entries:
1. A 16-bit transponder address, a
2. A 16-bit group identifier for the transponder, g
3. The LQoS for the transponder, l
4. A real number called the Effective LQoS (or ELQoS), e
5. A real number called the score, s
6. A bit called the slotswap bit, b.
A row in the table is described by an ordered six-type (a,g,l,e,s,b). A global flag called xe2x80x9cexcess-demandxe2x80x9d (to be described later) and an integer called xe2x80x9clast-groupxe2x80x9d are also maintained by the Scheduler.
When the Scheduler process is initialised, the scheduling table is empty. A single row (0,0,1,1,0, false) is immediately added. This entry represents a dummy transponder. The excess-demand flag is set to false, and the last-group is set to zero.
Adding or Changing a Request
An operator (user) or software application can contact the Scheduler over its CORBA interface to indicate that the location requests for a transponder group should be added or changed. It should be noted that if two or more transponders are members of the same transponder group then their location requests should not be capable of being added or changed separately. Furthermore, the requests involving the dummy transponder address 0 and dummy transponder group ID 0 will be ignored. The user or application passes the following information to the scheduler:
g, the transponder group identifier
l, the desired LQoS for members of this transponder group
a1, . . . , an, the transponder address of members of this transmitter group.
For each transponder address a1, . . . an, the scheduler then adds or modifies an entry in the scheduling table.
For values of i between 1 and n, if a row of the form (a1, g1, l1, e1, s1, b1) is present in the table, it is updated to (a1, g, l, e1, s1, b1) , otherwise a row (ai, g, l, 0, 0, false) is added.
The scheduler is then arranged to recalculate the ELQoS for each of the m entries in the table.
First, it calculates the total level of LQoS demand, (t), where t is given by Equation (1).
Next it updates the ELQoS for each of the n entries in the scheduling table, ei, with a new value exe2x80x2i. If t is less than 1, then exe2x80x2i is given by Equation (2).
Otherwise, if t is greater than or equal to 1, exe2x80x2i is given by Equation (3).
Deleting a Request
When a user or application contacts the Scheduler over its CORBA interface to indicate that a location request for a transponder should be deleted, it also passes the address of that transponder ai, to the Scheduler. (The entry corresponding to transponder address 0 may not be removed). If the scheduler finds that an entry for that transponder is present in the table, it removes the corresponding row (ar, gr, er, sr, br) from the table. The scheduler then updates every other row in the table (ax, gx, lx, ex, sx, bx) to (ax, gx, lx, ex, sxe2x80x2x, bx) where the value of Sxe2x80x2x is given by Equation (4),
In Equation (4) n is equal to the number of rows in the table before removal of the location request. The scheduler recalculates the effective rates based on the remaining table entries as described in the previous section.
Allocating Timeslots
Once every 40 ms, the Scheduler must tell the central coordinating device (across a CORBA interface) the address of the transponder which should we located next. It does this by examining the contents of the scheduling tabe and any attempts to update the table are blocked until this examination is complete.
First, the scheduler steps through each row in the scheduling table. If the last-group register does nor contain 0, and the scheduler encounters a row in which the transponder group ID is the same as the contents of the last-group register, and in which the swap-slot bit is false, it sends the transponder address contained in that row to the coordinating device, and sets the swap-slot bit on that row to xe2x80x9ctruexe2x80x9d.
Otherwise, the Scheduler operates in accordance with the following algorithm: (5)
1. Choose the row in the table with the highest score (ac, gc, lc, ec, sc, bc).
2. If bc is false, for each row of the table which has the transmitter group ID gc set the swapslot bit to false. Then, update each row in the table (ax, gx, lx, ex, sx, bx) to (ax, gx, lx, ex, sxe2x80x2x, bx) where sxe2x80x2x is given by
sxe2x80x2x=(sx+1/ex)
Next, the single chosen row in the table is further updated to (ac, gc, lc, ec, sxe2x80x3c, bc) where sxe2x80x3c(=sxe2x80x2.cxe2x88x921).
The lastgroup register is set to gc.
Finally, the coordinating device is informed of the address ac of the transponder that should be located next (if ac is zero, this indicates that no transponder should be addressed in the next timeslot)
3. If bc is true, update each row in the table (ax, gx, lx, ex, sx, bx) to (ax, gx, lx, ex, sxe2x80x2, bx) where sxe2x80x2x can be computed as above. Next, the single chosen row in the table is further undated to (ac, gc, lc, ec, sxe2x80x3c, false) where sxe2x80x3x=(sxe2x80x2.cxe2x88x921). The row in the scheduling table with the highest score is chosen again, and the above steps are retaken.
Rotational Movement
The relative positions of two or more transponders carried by the same object can be checked against the previous known positions to determine whether or not the object has for example been rotated.
According therefore to another feature or fine invention, a set of two or more transponders which are carried by the same object can be identified as such with a further item of information in their associated WHISPS, such that the control system will schedule the interrogation of second and any subsequent transponder addresses of the set of transponders on the object after the first of the pair has been interrogated.
By interrogating the set of transponders on an object in rapid succession so any relative movement between position determination of each point is minimised, rendering the orientation picture of the object from each such succession of position determinations to be as accurate as possible.
In general three transducers are needed to permit the orientation (and any changes in orientation) of an object to be determined. For some objects normally constrained to occupy a limited range of positions only two or even one transducer may be sufficient.
The invention also lies in apparatus for performing any of the above methods, and in particular comprises a master radio transmitter for transmitting short duration radio frequency trigger signals into an environment; a plurality of radio receiver-controlled ultrasound transmitter units (transponders; located on movable objects throughout the environment; a plurality of ultrasonic receivers located at fixed, spaced apart points in the environment and adapted to receive ultrasound signals from transponders in the environment; a coordinating control system adapted to cause the master radio transmitter to emit appropriately encoded trigger signals to trigger one particular transponder (if present) in the environment, and cause it to emit ultrasonic radiation; and a computer based data processing system receptive of signals from the ultrasound receivers for determining from the transit times associated with those transmissions the apparent line of sight distances of the transponders from at least some of the receivers, and thereby from the geometry of the receivers the apparent position of the object in the environment; memory means for storing position data for each such identified transponder and therefore the object on which it is mounted; scheduling means for determining the encoding of the next radio trigger transmission, and therefore the address of the next transponder whose position is next to be interrogated; additional memory means for storing at least one additional item of information in association with the position data of each transponder; and programmable data processing and/or logic means for determining from the said additional items of information and/or from at least one previously interrogated transponder address, which transponder address is to determine the next encoding of the radio trigger transmission.
In a preferred arrangement, further memory means is provided within which is stored data relating to the time at which each transponder address was last interrogated, and the programme running in the processor controlling the said logic means is adapted to compare the information stored in each said further memory means with the WHISP data for all transponder addresses suspected to be in the enviroment, to determine which of the transponders is next to be interrogated, and to encode the next radio trigger signal accordingly.
The different memory means may comprise different parts of one memory device (such as a large random access memory) or may be formed from two or more different memory devices, at least some of which may be random access memories and others may be programmable read only memories.
Reduction of Errors Due to Spurious Acoustic Signals
Obviously any acoustic noise sources in the environment which can generate ultrasonic signals similar to those sent by the ultrasound transmitters, have the potential to introduce false position determination.
In order to overcome this problem, and in accordance with another feature of the invention, the ultrasonic receiver is rendered sensitive only to sound of a particular frequency, by the use of an ultrasonic detector with a narrow bandwidth around that frequency, and the bandwidth of the sound signal emitted by the transmitter is also limited to a narrow bandwidth around that frequency, and wherein the system includes a further ultrasonic receiver adapted to simultaneously monitor sound at at least one of a number of different frequencies, and a logic based system determines if signal detected by a receiver at the unique frequency used by the transmitter is accompanied by other sounds at some or all of the said different frequencies and if not, the detected signal is identified as being TRUE, and if accompanied by other sounds, the detected signal identified as being corrupted by noise.
Thus for example noise sources in the environment (for example, a set of jangling keys) tend to simultaneously generate signals at a large number of different frequencies, so that sounds are detected at the transmitter frequency and at other frequencies simultaneously. The detection of such a range of sound signals (even though it contains a component at the transmitter frequency) has to be identified as either a FALSE sound signal or is as a TRUE signal which has been corrupted by noise, and in either event the signal must be rejected.
The number of additional frequencies that are monitored is preferably greater than one, and the monitoring may be performed at one or more of a number, of different points in the environment.
Orientation Determination
In some circumstances, a plurality of transponders may be attached to the same object. Thus if three transponders are attached to a rigid object so that they are not colinear, then by finding the positions of those three transponders not only the position but also the orientation of the object may be deduced (assuming that no movement of the object has occurred between the time at which the measurements were made).
Component Redundancy Reduction
Typically each transponder has its own independent radio interface, controlling log, and one or more ultrasonic transducers. However, where two or more such transponders are placed on an object, complete physical independence of the transmitters is not required and components of different transmitters can be interconnected using wires and duplication of components which are common to the transponders can be reduced or eliminated.
According to one aspect of the invention, a single radio receiver may be provided together with decoding logic to drive a number of individually addressable ultrasonic transducers. Thus the one receiver will respond to more than one address and hence can be described as a Multiple-Address transponder but for each address only one of the ultrasonic transducers would be triggered, corresponding in each case to one of the points on the object.
The invention thus envisages an object having mounted thereon a plurality of ultrasonic transducers located at a corresponding plurality of different non-colinear positions on the object, and a single radio receiver adapted to trigger one or another of the transducers depending on an address code contained within a radio signal received thereby, so that the different transducers may be triggered by appropriately coded radio signals, to transmit ultrasound signals into the environment at specific times, and from the different points on the object, to enable the unique positions of the said points on the object to be determined and enable the orientation of the object to be determined.
The invention also envisages each transducer as being comprised of a group of two or more similar transducers facing in different directions to more uniformly spread the ultrasound around the environment.
Ultrasonic Transmitter Design
In a preferred embodiment, the basic ultrasonic transmitter incorporates a plurality of ultrasonic transducers which are driven simultaneously to create a pulse of ultrasound from the device.
Typically, the transducers (which, individually, have a relatively narrow beam angle) are arranged to point in different directions so as to generate a generally omnidirectional transmission pattern. However, it is possible to arrange the transducers so as to produce a more directional beam, and two advantages follow:
1. The number of transducers required can be reduced. This is especially relevant if a transmitter is to be placed on an ultrasonically opaque object in such a way that if an omnidirectional signal were to be generated by the device a known fraction of the omnidirectional signal would be absorbed. A directional beam extending over the area not absorbed by the opaque object can therefore be generated using fewer transducers than would have been required to generate the omnidirectional signal, but the ultrasound signal issuing from the object will appear to be the same, as if an omnidirectional source had been employed.
2. The orientation of an object may be determined by identifying the positions in the environment at which receivers are located which receive signals from a transducer or the object. Thus directional transducer on the front of a computer monitor may be sufficient to enable the direction in which the screen is facing to be determined, by mapping which of the receivers on the environment xe2x80x9chearxe2x80x9d the transmitted ultrasound.
Power Saving
Standard operation of each transponder leaves the radio channel open continuously. This technique ensures that it will receive all addressing messages from the coordinating device, but if the transponder is battery powered it is also disadvantageous, in that power is used continuously by the radio interface and the batteries will become rapidly discharged.
According to another aspect of the present invention, the transponders are made aware of the fixed interval which is to occur between addressing messages and power saving is achieved by turning off the radio interface after a message is received and switching it on just before the next one is due.
This may be achieved by providing the transponders with a low-power supervisory circuit which can turn the radio interface on and off.
Further power saving may be achieved if the frequency with which a particular receiver-transmitter will be addressed by the coordinating device is known. If the coordinating device as programmed so as to be aware that the transponder will not be addressed for some amount of time, it can encode that time in the radio message, and after decoding the message the transponder will be able to switch off its radio interface for that amount of time. The power savings is particularly efficient if a transmitter is made to xe2x80x9csleepxe2x80x9d for a long time, as would be the case if the transponder is being used to track, an item of office equipment such as a printer, which is not expected to move very often.
The scheme described above can be extended so allow sleeping transponders to be woken up at short notice. Thus in the case in which the coordinating device is sending out 50 addressing messages each second, the transponders can be configured so that they turn on their radio interfaces once a second, at a time when a message is due, and decode that message (therefore using {fraction (1/50)} of the power which would have been used if they had decoded each message). A data bit at the start of each message (the wake bit) indicates that the coordinating device wishes to wake up all sleeping transponders or a set of sleeping transmitters (say, all those with even addresses). If a number of bits can be transmitted at the beginning of each transmission, the xe2x80x9csleepingxe2x80x9d transponder can be grasped and woken up accordingly by transmitting an appropriate code, within the capability of the bits. If a sleeping transponder receives such a message, and if that message is applicable to it, it will wake up, and from that time on check every addressing message from the coordinating device, until such time that it is instructed to go to sleep again. With this method, much of the power-saving advantage of sleeping can be retained, and yet it can quickly trigger transponder so as to be able to determine its location. Thus in the case of the printer described above, if a person walked up to the printer, it is likely that they might move the printer, and in which event it may need to start tracking it immediately, even if it was currently xe2x80x9csleepingxe2x80x9d to save power.
If a transponder is taken out of range of the master radio attached to the coordinating device, there is no point in it continually turning on its radio interface, for it will be unable to receive addressing messages. Therefore, in order to save power in these circumstances, if a transponder does not receive an addressing message at a time when one is expected, then it can be programmed to go into sleep mode for a predetermined period (perhaps one minute), before turning the radio channel on again for sufficient time to detect whether it is in range of the coordinating device again. For example, if the coordinating device was sending out an addressing message every {fraction (1/50)} second, then a sleeping transmitter must wake for {fraction (1/50)} second to determine if it is in range of that coordinating device. If it did this once a minute, then the radio interface would use only {fraction (1/300)} of the power it would otherwise use. This is achieved at the expense or up to a one minute delay before a transponder""s position can be determined after it is back in range of the coordinating device.
Registration of New Transponders as They Enter an Environment
It is desirable for such a system to be able to cope with the introduction of a previously xe2x80x9cunknownxe2x80x9d transponder unit without operator intervention. In this situation there is a requirement to indicate to the overall coordinating device that it must start to address the new transponder. This process will be referred to as a xe2x80x9cregistrationxe2x80x9d. It is merely necessary that the new transponder is compatible with and has a radio address which is one that would be expected and recognised by, the system.
In order to do this and in accordance with a preferred feature of the present invention, a bi-directional radio link is provided between a remote receiver and each transponder. Typically this is achieved by adding a radio transmitter to each transponder and adding a radio receiver to the master transmitter. Such transponders will be referred to as bi-directional transponders.
In one arrangement the coordinating device may for example transmit the radio receiver addresses in sequence of all possible bi-directional transponders, at regular intervals. The bi-directional transponder radio responses may be checked for radio responses from any new transponder addresses, and these addresses may then be added to the list of bi-directional transponder addresses which are to be scheduled, for position determination by subsequently triggering by radio their bi-directional transponder so as to generate ultrasound signals.
In a more preferred arrangement a xe2x80x9cSlotted ALOHA contention-resolution protocolxe2x80x9d such as described by Roberts L in ALOHA Packet Systems With and Without Slots and Capture, Computer Communications Review, April 1975, may be used to allow the transponder to identify its unique identification (ID) to the coordinating device and establish its position in the schedule for the master transmitter.
This type of protocol is a probabilistic protocol which allows many transmitting and receiving devices to use the same radio channel to transmit at the same time. This allows a plurality of transponders to use the same radio channel to communicate with the coordinators and enter their ID""s into the schedule to be used by the master transmitter.
Preferably the contention-resolution protocol is performed until an indication is received from the master transmitter and/or its associated coordinator that location resources have been allocated to the new ID for that transponder transmitter.
This indication may be sent as part of the addressing message.
The indication may simply be a command to transmit or a separate acknowledgement field.
In either case, the transponder""s unique radio receiver ID may be encoded in the message to show that the master transmitter and/or coordinator is aware of its presence.
Resource Retrieval
This has been referred to above, and in accordance with another feature of the invention, xe2x80x9cregistrationxe2x80x9d may also be used in resource retrieval to prevent valuable resources being used unnecessarily.
Thus if a bi-directional transponder is moved to a location where its ultrasonic signal is undetectable (e.g. if it is placed in, a box) then the coordinating device may be programmed to reallocate the location resources that were are being used to track that device.
For example if no ultrasound signal from a bi-directional transponder has been detected after it has been addressed for say up to four times, the coordinating device may be programmed to set a xe2x80x9ctransmitxe2x80x9d bit in the radio addressing message the next time it is transmitted by the master transmitter, so as to force a registration from the addressed transponder transmitter, whilst blocking registration attempts from any other bi-directional transponders.
If a radio reply from the bi-directional transponder transmitter is detected by the master radio receiver in response to a xe2x80x9ctransmit bitxe2x80x9d, then the related object mounted transponder is still in range of the master radio transmitter, and the absence of an ultrasound response either lies in a temporary shielding of the transponder or an electrical failure, (as opposed to movement of the object), and the resource should not be reclaimed. In the example given the transponder may have been temporarily shadowed by ultrasound absorbing material.
If no signal is detected, then the next time that bi-directional transponder is addressed by the master radio transmitter the coordinating device may be programmed to set a special drop bit in the addressing message, to indicate that the location resources that are currently allocated to that transponder will be reclaimed, and the transponder concerned will not subsequently be addressed via the master transmitter radio link.
If the transponder radio receiver can receive this message, it must be in a location where it can receive radio signals from the master radio transmitter but the coordinator is unaware of its ultrasonic response. In this event the bi-directional transducer is programmed to perform the registration process described above, but in the meantime the coordinating device reclaims the now unused location resource associated with that ID, until such time as the transducer achieves registration.
The use of a drop bit dictates that the radio interface should be very reliable, since if a transponder were to miss a message telling it not to expect any more radio addressing transmissions this could result in the transponder not starting the registration process, and, without other intervention, no further position updates would be received for that transponder.
According to a preferred feature of the invention, each addressing message contains one or more sets of error-correcting or error-detecting bits in combination with a powerful checking algorithm (e.g. CRC Check).
If a transponder receives a message containing errors, it is programmed to assume that the message was destined for it, and that the drop bit was set, so that if a transponder receives such a message, it will immediately begin the registration process.
Whether there are merely a number of independent but interlinked regional coordinators, or an overall coordinating device which sits above a plurality of regional coordinating devices, either the overall device or all of the regional coordinating devices (or both) may be programmed to remember the ID""s of any bi-directional transponders which have dropped out, and this fact may be compared with a look up table of data, indicating whether or not an alarm is to be raised and/or the absence noted in a display. For example in the case of an ID associated with a valuable piece of apparatus, a burglar alarm may be sounded, and exit down remotely locked.
Likewise, if an ID is discovered in a region in which it should not be (eg a person or a container of dangerous material) then the overall coordinator (or the regional coordinators) may likewise be Programmed to raise an alarm, bar access or exit, and/or display this in a display.
Transmission of Additional Information
According to another feature of the invention, input and output facilities may be provided on the transponders.
For example, in addition to the address of the device that is being requested to transmit the ultrasonic pulse, a radio message from a coordinating device may contain a number of data bits (an xe2x80x9cOutput Data Valuexe2x80x9d) which may, for example, be sent to an output port on the addressed transponder, to control for example a display, or robotic device associated with that transponder.